package sit.engreal.leetcode.problems800;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/letter-case-permutation/">784. 字母大小写全排列</a>
 */
public class LeetCode784 {
    public List<String> letterCasePermutation(String s) {
        final List<String> list = new ArrayList<>();
        int[] p = new int[s.length()];
        int n = 0;
        final char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (Character.isAlphabetic(str[i])) {
                p[n] = i;
                n++;
            }
        }
        for (int i = 0; i < (1 << n); i++) {
            final StringBuilder builder = new StringBuilder();
            int k = 0;
            for (int j = 0; j < str.length; j++) {
                final char ch;
                if (j == p[k]) {
                    if (((i >>> k & 0x1) == 1)) {
                        ch = Character.toUpperCase(str[j]);
                    } else {
                        ch = Character.toLowerCase(str[j]);
                    }
                    k++;
                } else {
                    ch = str[j];
                }
                builder.append(ch);
            }
            list.add(builder.toString());
        }

        return list;
    }

    public static void main(String[] args) {
        final LeetCode784 demo = new LeetCode784();
        System.out.println(demo.letterCasePermutation("3z4"));
        System.out.println(demo.letterCasePermutation("a1b2"));
        System.out.println(demo.letterCasePermutation("abc"));
    }
}
